/* 

  插入排序,
    从 0-0, 0-1 , 0-2 不断插入排序

    时间复杂度与数据状况有关


*/

function insertionSort(arr) {
  if (!arr || arr.length < 2) return

  for (let i = 1; i < arr.length; i++) {
    //0-i做到有序
    for (let j = i - 1; j >= 0 && arr[j + 1] < arr[j]; j--) {
      ;[arr[j + 1], arr[j]] = [arr[j], arr[j + 1]]
    }
  }
}

let o = [1, 10, 4, 3, 6, 2, 5, 9]
insertionSort(o)
console.log(o)
